﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/// <summary>
/// 三种遍历（前序，中序，后序）
/// </summary>
namespace BinarTtree.Traversal
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class MainProject
    {
        //q
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            //TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
            TreeNode treeNode = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));

            foreach (var item in PreorderTraversal(treeNode))
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }

        public static IList<int> PreorderTraversal(TreeNode root)
        {
            List<int> preList = new List<int>();
            Preorder(root, preList);
            return preList;
        }

        public static void Preorder(TreeNode treeNode, List<int> list)
        {
            if (treeNode == null)
            {
                return;
            }
            //前续遍历
            Preorder(treeNode.left, list);
            list.Add(treeNode.val);
            Preorder(treeNode.right, list);

            //中续遍历
            Preorder(treeNode.left, list);
            list.Add(treeNode.val);
            Preorder(treeNode.right, list);

            //后续遍历
            Preorder(treeNode.left, list);
            Preorder(treeNode.right, list);
            list.Add(treeNode.val);
        }

    }
}
